1. Field of the Invention
The present invention relates to a line drawing method, and particularly to a line drawing method that utilizes the nature of memory access to determine and draw multiple points at a time, thereby speeding up line drawing.
2. Description of the Related Art
Modern computer video display devices usually consist of a regular grid of small points of light (pixels), each of which can be independently lit with a color (hue) and an intensity (brightness). One of the most fundamental problems in computer graphics is that of determining which set of pixels best represents an image, and which colors and intensities to assign to those pixels so that straight lines and edges can be drawn on a computer display.
FIGS. 1A, 1B and 1C illustrate the relationship between pixels on screen and memory access. FIG. 1A shows a pixel P with coordinate (x,y) on screen 10 corresponds to location in display buffer. However, a memory operation is able to access data for a plurality of pixels instead of just one. We take a true-color resolution (32 bits for each pixel) display for example. For a memory bus with 128-bit data bus width, a data transfer (block 20) will contain data for four pixels (21, 22, 23 and 24) at one time as illustrated in FIG. 1B. That is, every four pixels are grouped as a block 20 for a memory access unit, as illustrated in FIG. 1C.
The first step in drawing a straight line or edge on a computer display is to determine which pixels on the display most closely approximate the line. A famous algorithm commonly used is Bresenham's algorithm. Before explaining the algorithm, it is necessary to define a few terms. An X-major line lies more horizontally than vertically. The “major axis” of such a line refers to the X-axis, while the “minor axis” refers to the Y-axis. Similarly, a line that lies more vertically than horizontally is a Y-major line. The “major axis” of such a line refers to the Y-axis, while the “minor axis” refers to the X-axis.
FIG. 2 shows an example of an x-major integer Bresenham line-drawing algorithm. In Bresenham's algorithm, lines are drawn using integer math; division is not performed and fractions are not used. Bresenham's algorithm enjoys perfect accuracy and full precision and, hence, draws mathematically perfect lines.
Suppose an x-major line is drawing from P1(1,1) to P2(10,3) in display buffer 11 as illustrated in FIG. 3A. That is, there are three blocks (31, 32 and 33) of pixels for memory access as illustrated in FIG. 3B. FIG. 3C illustrates the line drawing sequence. Ten pixel-drawing operation are needed, namely, ten processing cycles may require for the line drawing. Therefore, even though a memory access can handle the data for four pixels, the performance of line drawing using Bresenham's method is not satisfactory because it determines and draws one point at a time.